This invention relates to image processing. More particularly, the invention relates to a system and method of processing a list of triangles that represent a surface of a three-dimensional object image.
Image processing systems are capable of converting graphical object data into an image that is viewed by a user or observer of the image processing system. Graphical object data may be stored in a variety of different formats, including various compressed formats. The type of data format used to store the graphical object data varies depending on the type of image processing system that receives and processes the data, the type of image being produced (e.g., two-dimensional or three-dimensional), and the type of equipment used to generate and store the graphical object data.
In three-dimensional graphics applications, graphical objects are typically defined, processed, and provided to the rendering hardware as a series of adjoining triangles. Each triangle is defined by three points or vertices. Because the triangles adjoin each other, a single point might be a vertex of several different triangles.
Each point or vertex of each triangle may have various associated information, such as location coordinates (i.e., coordinates in the x, y, and z directions), ambient color, reflective color, texture coordinates, fogging and alpha blending components, etc. Since each vertex may have a significant amount of associated data, operations such as moving, storing, and reading vertices can become a significant part of the image rendering process.
FIG. 1 illustrates an exemplary rendering module 10 that receives graphical object data and generates a rendered image. Rendering module 10 receives graphical object data 12 from a data source. The rendering module 10 processes the graphical object data 12 and generates a rendered image 14. The rendered image 14 can be displayed on a computer monitor or other display device or may be transmitted to another location for display.
FIG. 2A illustrates a series of five triangles, labeled T1-T5. Each triangle has three vertices, labeled xe2x80x9c1xe2x80x9d, xe2x80x9c2xe2x80x9d, and xe2x80x9c3xe2x80x9d. Adjacent triangles share vertices with one another. For example, triangles T1 and T2 share two verticesxe2x80x94vertex 2 of triangle T1 is shared with vertex 2 of triangle T2 and vertex 3 of triangle T1 is shared with vertex 1 of triangle T2.
A series of triangles, such as the series shown in FIG. 2A, can be represented in several formats: a non-indexed list, a non-indexed strip, an indexed list, and an indexed strip. A non-indexed list identifies three separate vertices for each triangle in the series. For example, in the series of triangles shown in FIG. 2A, a non-indexed list is represented as:
T1: T1V1, T1V2, T1V3
T2: T2V1, T2V2, T2V3
T3: T3V1, T3V2, T3V3
T4: T4V1, T4V2, T4V3
T5: T5V1, T5V2, T5V3
Where, for example, T1V1 defines vertex xe2x80x9c1xe2x80x9d of triangle T1 and T1V2 is vertex xe2x80x9c2xe2x80x9d of triangle T1. Each entry in the list (T1V1, T1V2, etc.) represents a triangle vertex and has associated information, as discussed above (i.e., screen coordinates, color, etc.). This non-indexed list requires three separate vertex entries to define each triangle. Further, the non-indexed list does not consider the common relationships between certain vertices (e.g., in FIG. 2A, T1V2 is the same vertex as T2V2, and T1V3 is the same vertex as T2V1). Thus, when processing the non-indexed list, the system will process both vertices T1V2 and T2V2, even though they are the same vertex. This results in unnecessary vertex processing, which reduces the performance of the image processing system. However, the list format is advantageous in that a single list is able to store an entire mesh of triangles (discussed below).
In a non-indexed strip of triangles, a list of vertices represents a single triangle strip. Each vertex in the non-indexed strip (starting with the third vertex) defines a triangle along with the two previous vertices. FIG. 2B illustrates the same five triangles illustrated in FIG. 2A, but each of the seven vertices has a single identifier (labeled 1-7). The five triangles in FIG. 2B can be represented by the following triangle strip:
V1, V2, V3, V4, V5, V6, V7
where V1 through V7 each define a single vertex. This triangle strip represents triangles (V1, V2, V3), (V3, V2, V4), (V3, V4, V5), (V5, V4, V6), and (V5, V6, V7). A strip of triangles is an efficient way to represent a series of adjacent triangles. However, the triangle strip format cannot generally represent an entire mesh of triangles as a single strip. Instead, multiple strips are required to represent the triangle mesh. Each time the strip reaches a triangle with no other adjoining triangle, the current strip terminates and a new strip is started.
Using an indexed list notation, a list of three indices is associated with each triangle and a pool of vertices is referred to by the indices. For example, using an indexed list to identify the five triangles in FIG. 2B, the indexed list is represented as:
V1, V2, V3, V4, V5, V6, V7
and the associated indices:
i1, i2, i3
i3, i2, i4
i3, i4, i5
i5, i4, i6
i5, i6, i7
In this notation, xe2x80x9cV1xe2x80x9d defines a first vertex and the indices xe2x80x9ci1 i2, i3xe2x80x9d define the first triangle as having vertices V1, V2, and V3. The indexed list vertices can be processed once into a separate buffer so that the indexed accesses can read pre-processed vertices. Using this process, each distinct vertex is processed exactly once. Another advantage of the indexed list is its reduction in storage size (an index is very small (e.g., two bytes) compared to a vertex (e.g., 32 bytes).
Finally, an indexed strip of triangles identifies a strip of indices and a pool of vertices referred to by the indices. For example, using an indexed strip to represent the five triangles in FIG. 2B produces a sequence of vertices:
V1, V2, V3, V4, V5, V6, V7
and associated indices:
i1, i2, i3, i4, i5, i6, i7
Using this notation, xe2x80x9cV1xe2x80x9d defines a first vertex of a triangle in the strip and the first three indices xe2x80x9ci1, i2, i3xe2x80x9d define the first triangle in the strip. The indexed strip of triangles provides a simplified notation for representing triangle strips.
FIG. 3 illustrates an example mesh of triangles 20 (also referred to as a xe2x80x9ctriangle meshxe2x80x9d). In a typical mesh of triangles, each vertex is usually shared by six triangles. Rather than processing the same vertex six times (once for each triangle associated with the vertex), known techniques simplify the processing by: (1) processing the mesh of triangles using indices to refer to vertices in a pool of unique vertices so that each vertex only needs to be transformed (or processed) once, and (2) if a sequence of adjacent triangles exists (such as a mesh), treating the sequence as a xe2x80x9ctriangle stripxe2x80x9d instead of a xe2x80x9ctriangle list.xe2x80x9d Using the second technique, the first triangle is defined by three vertices. All subsequent triangles are defined by a single new vertex and the last two vertices of the previous triangle in the strip. These two techniques can be used separately or together so that existing graphics systems can handle the following combinations: Non-Indexed List, Non-Indexed Strip, Indexed List, and Indexed Strip.
Using these known techniques, many vertices are processed only once for all associated triangles, rather than repeatedly processing the same vertex for different associated triangles. Thus, many existing systems attempt to process triangles in strips instead of individual triangle lists. However, in many situations, it is easier to define and maintain the triangles in a triangle list format instead of a strip format. For example, a mesh may include physically disconnected groups of triangles that otherwise share similar features (such as similar texture). These triangles can be grouped together in a list but cannot be connected as a strip because the triangles are not physically adjacent to one another (a requirement to form a strip of triangles). Additionally, it is generally difficult to define an entire mesh of triangles as a single strip. The shape of the mesh may prevent creation of a single strip or may require the insertion of xe2x80x9cdummyxe2x80x9d triangles to convert the mesh into a single strip.
The image processing begins when an application passes the graphical object data 12 (FIG. 1) to the rendering module 10 through an interface method. The available interface methods expect to receive data in one of the formats discussed above. Another problem associated with the use of triangle strips is caused by existing application programming interfaces (APIs) that can only process a single strip of triangles in one function call to the rendering module 10. Thus, a mesh that could be represented as a single list of triangles is instead passed through the API as multiple triangle strips, each of which incurs a function call overhead.
The invention provides an improved mechanism for converting a mesh of triangles represented as a list of triangles into one or more strips of triangles. Graphical object data (in triangle list format) is provided to a list optimization module, which rearranges the list of triangles to improve the generation of triangle strips from the triangle list. After rearranging the list of triangles, the list optimization module provides the rearranged list to a triangle processing module. The triangle processing module converts the list of triangles to multiple triangle strips. The multiple triangle strips are then processed by a rendering module to generate an image.
The invention described herein is capable of representing an entire triangle mesh as a single triangle list. The triangle list format, which provides for easier data manipulation, is maintained for most of the processing. However, the list optimization module rearranges the triangles in the indexed list and reorients the triangle indices by rotating the indices, as necessary, to optimize the processing of the indexed list of triangles. Specifically, the triangles are rearranged in adjacent strips even though they continue to be listed and stored in a non-strip format. The triangles are then provided to a triangle processing module in an indexed list, non-strip format, through the use of a single function call. The triangle processing module then converts the indexed triangle list into one or more triangle strips, which is made possible by the previous re-ordering of the listed triangles. Using this method, the benefits of strip processing can be obtained without incurring the overhead of multiple function calls. The triangle strips are easier to process by the rendering module or other rendering hardware due to the reduced number of vertices that require processing (as a result of the sharing of vertices between adjacent triangles). The rendering module uses the strips of triangles to generate an image on a display device, such as a computer monitor or a television.
In a particular implementation of the invention, the single vertex added to the current triangle strip is the vertex of the current triangle that is not already contained in the current triangle strip.
In another implementation of the invention, after terminating the current triangle strip, a new triangle strip is created starting with the current triangle. All three vertices of the new triangle are processed at the start of the new triangle strip.
In one embodiment of the invention, the triangle processing module determines whether the current triangle can be treated as a continuation of the current triangle strip by comparing a specific pair of triangle indices of the current triangle to a specific pair of triangle indices of the previous triangle. If the previous triangle in the current triangle strip is an odd triangle and the current triangle is an even triangle, and if the second index of the previous triangle matches the first index of the current triangle and the third index of the previous triangle matches the third index of the current triangle, then the current triangle is added to the current triangle strip. If the previous triangle in the current triangle strip is an even triangle and the current triangle is an odd triangle, and if the second index of the previous triangle matches the second index of the current triangle and the third index of the previous triangle matches the first index of the current triangle, then adding the current triangle to the current triangle strip.